import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
* 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。(非递归用栈)
 * */
class preorderTraversalNotDiGui {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode node=root;
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                ret.add(node.val);
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            node=node.right;
        }
        return ret;
    }
}